//
// Created by xili on 2024/8/28 19:12.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    long long maximumSumOfHeights(vector<int> &heights) {
        long long ans = 0;
        int n = heights.size();
        for (int i = 0; i < n; i++) {
            long long cur = acc(heights, i);
            ans = ans > cur ? ans : cur;
        }
        return ans;
    }

    long long acc(vector<int> &heights, int maxi) {
        int n = heights.size();
        int l = maxi, r = maxi;
        int cur = heights[maxi];
        long long ans = heights[maxi];
        while (l > 0) {
            if (heights[l - 1] >= cur) {
                ans += cur;
            } else {
                ans += heights[l - 1];
                cur = heights[l - 1];
            }
            l--;
        }
        cur = heights[maxi];
        while (r < n - 1) {
            if (heights[r + 1] >= cur) {
                ans += cur;
            } else {
                ans += heights[r + 1];
                cur = heights[r + 1];
            }
            r++;
        }
        return ans;
    }
};